package com.yincb.sort;

import com.sun.scenario.effect.Merge;

import java.util.Arrays;

public class ShellSort2 {


    public static void main(String[] args) {

        int[] data = {9, 5, 6, 8, 0, 3, 7, 1};
        int[] tem = new int[data.length];
        mergeSort(data, 0, data.length - 1, tem);

        System.out.println(Arrays.toString(tem));

    }

    private static void mergeSort(int[] data, int left, int right, int[] tem) {
        if (left < right) {
            System.out.println("left=" + left + " right=" + right);
            int mid = (left + right) / 2;
            mergeSort(data, left, mid, tem);
            mergeSort(data, mid + 1, right, tem);
            merge(data, left, mid, right, tem);
        }


    }

    private static void merge(int[] data, int left, int mid, int right, int[] tem) {
        int p1 = left;
        int p2 = mid + 1;
        int t = 0; // tem 临时下标
        while (p1 <= mid && p2 <= right) {
            if (data[p1] <= data[p2]) {
                tem[t] = data[p1];
                t++;
                p1++;
            } else {
                tem[t] = data[p2];
                t++;
                p2++;
            }
        }

        while (p1 <= mid) {
            tem[t] = data[p1];
            p1++;
            t++;
        }

        while (p2 <= right) {
            tem[t] = data[p2];
            p2++;
            t++;
        }

        t = 0;
        while (left <= right) {
            data[left] = tem[t];
            left++;
            t++;
        }
    }

}

